package algorithm.leetcode.primary.array;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 旋转数组
 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
 */
public class Rotate {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        //int[] nums = {-1,-100,3,99};
        int k = 3;
        //System.out.println(6%5);
        rotate4(nums,k);
    }

    //反转
    public static int[] reverse(int[] nums, int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            //位异或运算，按位对比，相同取0，不同取1,实际上就是交换值
            nums[j]^=nums[i];
            nums[i]^=nums[j];
            nums[j]^=nums[i];
        }
        /*for(int i=0;i<arr.length;i++){
            arr[i] = arr[arr.length-i-1];
            arr[arr.length-i-1] = arr[i];
        }*/
        return nums;
    }
    //三次反转
    public static void rotate4(int[] nums, int k){
        nums = reverse(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
        nums = reverse(nums,0,k%nums.length-1);
        System.out.println(Arrays.toString(nums));
        nums = reverse(nums,k%nums.length,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    public static void rotate3(int[] nums, int k) {
        int t1,t2,index,count = 0;
        int len = nums.length;
        k %= len;//对k值的前期处理，处理原因是如果k值比len大，那么只有大于len的那部分才是有效移动
        System.out.println(k);
        if(k == 0) return ;
        for(int i=0;i<=k;i++){
            if(count >= len) break;
            index = i;//每轮移动的初始下标
            t1 = nums[i];
            System.out.println("i:"+i);
            while((index + k)%len != i) //一个while循环移动一次
            {
                t2 = nums[(index + k)%len];
                nums[(index + k)%len] = t1;
                index = (index + k)%len;
                t1 = t2;
                count++;
            }
            nums[i] = t1;
            count++;
        }
        System.out.println(Arrays.toString(nums));
    }

    public static void rotate2(int[] nums, int k) {
        int n = 0;//移动次数
        int s = 0;//位置
        int push = nums[0];;//弹出
        int pull = 0;
        while(n < nums.length-1){
            for(int i=0;i<nums.length-1;i++){
                if((nums.length-i-k-1) == s){
                    System.out.println(i+"|"+s);
                    pull = nums[s];
                    nums[s] = nums[i];
                    nums[i] = pull;
                    s++;
                    n++;
                    System.out.println(Arrays.toString(nums));
                }
            }
        }
        nums[s] = push;

    }
    public static void rotate1(int[] nums, int k) {
        int[] tmp = new int[nums.length];
        for (int i=0;i<nums.length;i++){
            if(i+k > nums.length-1){
                tmp[i+k-nums.length] = nums[i];
            } else {
                tmp[i+k] = nums[i];
            }
        }
        System.out.println(Arrays.toString(tmp));
    }
}
